package com.奇数偶数结点链表交换;

public class Solution {
	public ListNode oddEvenList(ListNode head) {
		ListNode head2 = new ListNode(-1);
		ListNode temp = head2;
		ListNode p, q = null;// 用于指向原始链表
		p = head;
		while (p != null&&p.next!=null) {
			ListNode t=head2;
			q = p.next;// q代表第偶数个结点
			p.next = q.next;
			temp.next = q;
			q.next=null;//断开q与原来链表的联系
			temp = temp.next;
			// 对q的操作要先于对p的下一个节点的判断，不然会导致最后一个结点被忽略
			// 一定要有这个判断当p指向7且指向8后面的null值后，再执行p=p.next会造成空指针异常
			if (p.next == null) {
				// 即保证p指向的是最后一个奇数而不是一个空值
				break;
			}
			p = p.next;
		}
		// 此时p指向了最后一个结点
		p.next = head2.next;
		// head2是一个头结点初始化为-1与原来链表无关
		return head;
	}
}

class Solution1 {
	//pre =1 post=2 temp=pre.next
	/* 先用一个临时变量存储最后一个奇数后的偶数
	 * 奇数找到下一个奇数，偶数找到下一个偶数，然后将
	 * pre,post都往后移动一位指向各自奇偶列的最后一位
	 * 然后用pre指向临时变量将两个链表再次连接起来
	 * */
	//1->3 2->4->5
	//1->3->2->->5
    public ListNode oddEvenList(ListNode head) {
        if(head==null)return null;
        ListNode pre=head;
        ListNode post=head.next;
        //pre会一直指向奇数链表的最后一位。post会指向偶数链表的最后一位
        while(post!=null&&post.next!=null){
            //使用temp来临时存储奇数链表的后一位
            ListNode temp=pre.next;
            pre.next=post.next;
            post.next=post.next.next;
            pre=pre.next;
            post=post.next;
            pre.next=temp;
        }
        return head;
       
    }
}
